You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Return the number of connected components in the graph.
Example 1:
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2
Example 2:
Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1
Constraints:
1 <= n <= 20001 <= edges.length <= 5000edges[i].length == 20 <= ai <= bi < nai != bi- There are no repeated edges.
Average Rating: 4.68 (19 votes)
Solution
Approach 1: Depth-First Search (DFS)
Intuition
If you're not familiar with DFS, check out our Explore Card.
In an undirected graph, a connected component is a subgraph in which each pair of vertices is connected via a path. So essentially, all vertices in a connected component are reachable from one another.
Let's see how we can use DFS to solve the problem. If we run DFS, starting from a particular vertex, it will continue to visit the vertices depth-wise until there are no more adjacent vertices left to visit. Thus, it will visit all of the vertices within the connected component that contains the starting vertex. Each time we finish exploring a connected component, we can find another vertex that has not been visited yet, and start a new DFS from there. The number of times we start a new DFS will be the number of connected components.
Here is an example illustrating this approach.
Figure 1. An example demonstrating the DFS approach.
Algorithm
- Create an adjacency list such that
adj[v]contains all the adjacent vertices of vertexv. - Initialize a hashmap or array,
visited, to track the visited vertices. - Define a
countervariable and initialize it to zero. - Iterate over each vertex in
edges, and if the vertex is not already invisited, start a DFS from it. Add every vertex visited during the DFS tovisited. - Every time a new DFS starts, increment the
countervariable by one. - At the end, the
countervariable will contain the number of connected components in the undirected graph.
Complexity Analysis
Here E = Number of edges, V = Number of vertices.
-
Time complexity: O(E+V).
Building the adjacency list will take O(E) operations, as we iterate over the list of edges once, and insert each edge into two lists.
During the DFS traversal, each vertex will only be visited once. This is because we mark each vertex as visited as soon as we see it, and then we only visit vertices that are not marked as visited. In addition, when we iterate over the edge list of each vertex, we look at each edge once. This has a total cost of O(E+V).
-
Space complexity: O(E+V).
Building the adjacency list will take O(E) space. To keep track of visited vertices, an array of size O(V) is required. Also, the run-time stack for DFS will use O(V) space.
Approach 2: Disjoint Set Union (DSU)
Imagine we have a graph with N vertices and 0 edges. The number of connected components will be N in that graph.
Let's now add the edge from vertex 1 to vertex 2. This will decrease the number of components by 1. This is because vertices 1 and 2 are now in the same component.
When we then add the edge from vertex 2 to vertex 3, the number of components will decrease by 1 again.
However, this pattern will not continue when we add the edge from vertex 1 to vertex 3. The number of components will not change because vertices 1, 2, and 3 are already in the same component.
The above observation is the main intuition behind the DSU approach.
Algorithm
- Initialize a variable
countwith the number of vertices in the input. - Traverse all of the edges one by one, performing the union-find method
combineon each edge. If the endpoints are already in the same set, then keep traversing. If they are not, then decrementcountby 1. - After traversing all of the
edges, the variablecountwill contain the number of components in the graph.
Complexity Analysis
Here E = Number of edges, V = Number of vertices.
-
Time complexity: O(E⋅α(n)).
Iterating over every edge requires O(E) operations, and for every operation, we are performing the
combinemethod which is O(α(n)), where α(n) is the inverse Ackermann function. -
Space complexity: O(V).
Storing the representative/immediate-parent of each vertex takes O(V) space. Furthermore, storing the size of components also takes O(V) space.
April 6, 2021 12:33 AM
Pyton union find solution
class DSU:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0 for _ in range(n)]
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
xset = self.find(x)
yset = self.find(y)
if xset == yset:
return
if self.rank[xset] > self.rank[yset]:
self.parent[yset] = self.parent[xset]
elif self.rank[xset] < self.rank[yset]:
self.parent[xset] = self.parent[yset]
else:
self.parent[xset] = self.parent[yset]
self.rank[yset] += 1
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
ds = DSU(n)
for edge in edges:
ds.union(edge[0], edge[1])
parent = set()
for i in range(n):
parent.add(ds.find(i))
return len(parent)
April 16, 2021 3:59 AM
Python DFS Solution:
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
count = 0
graph = [[] for _ in range(n)]
seen = [False for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
def dfs(node):
for adj in graph[node]:
if not seen[adj]:
seen[adj] = True
dfs(adj)
for i in range(n):
if not seen[i]:
count += 1
seen[i] = True
dfs(i)
return count
April 11, 2021 4:30 AM
shouldn't the answer to this input be 1? [[2,3],[1,2],[1,3]]
because all the nodes are connected. Don't understand why it would be 2.
very confusing.
based of their sample inputs and outputs in the description, the output for the input in question should be 1.
this is my python solution.
class Solution(object):
def countComponents(self, n, edges):
from collections import defaultdict
adjacency_list = defaultdict(list)
for cNode, nNode in edges:
adjacency_list[cNode].append(nNode)
adjacency_list[nNode].append(cNode)
seen = {}
i = 0
keys = list(adjacency_list.keys())
while keys:
i += 1
stack = [keys[0]]
while stack:
parent = stack.pop()
for child in adjacency_list[parent]:
if child in seen:
continue
seen[child] = True
stack.append(child)
keys.remove(child)
return i
May 4, 2021 11:12 AM
Union-find solution is fun.
One nitpick is time complexity of the UF solution introduces the undefined n in a(n). Yet V is not used, although for (int i = 0; i < n; i++) suggests that it impacts the time complexity.
May 3, 2021 3:18 AM
Can someone please explain ''α(n) is the inverse Ackermann function''
May 15, 2021 5:24 AM
Why is this two components? Its just one group isnt it?
4
[[2,3],[1,2],[1,3]]
May 2, 2021 9:37 AM
Another possible solution is using BFS. We keep a set of non-visited nodes and while it is not empty, we pop a 'seed' out of it to start a BFS, over which we can remove all the connected nodes from the non-visited nodes. We increment count each time we pop a 'seed'. Note I haven't used a variable called 'seed', but it's what "not_seen.pop()" yields.
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
graph = [list() for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
not_seen = set(i for i in range(n))
count = 0
while not_seen:
q = [not_seen.pop()]
count += 1
while q:
next_q = list()
while q:
for node in graph[q.pop()]:
if node in not_seen:
not_seen.remove(node)
next_q.append(node)
q = next_q
return count
May 1, 2021 7:34 PM
Python solution -
class Solution(object):
def countComponents(self, n, edges):
parents = list(range(n))
def find(u):
if u != parents[u]:
parents[u] = find(parents[u])
return parents[u]
for u, v in edges:
parent_of_u = find(u)
parent_of_v = find(v)
parents[parent_of_u] = parent_of_v
map(find, range(n))
s = set()
for i in parents:
s.add(i)
return len(s)
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int countComponents(int n, vector<vector<int>>& edges) { }};